package leetcode.biweekly.week79;

public class BookMyShow {

	int n, m;
	int[] rest;

	public BookMyShow(int n, int m) {
		this.n = n;
		this.m = m;
		this.rest = new int[n];
		for (int i = 0; i < rest.length; i++) {
			rest[i] = m;
		}
	}

	public int[] gather(int k, int maxRow) {
		int l = 0, r = maxRow;
		int ans = -1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (rest[mid] >= k) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		if (ans == -1) {
			return new int[] {};
		}
		for (int i = 0; i <= ans; i++) {
			if (this.rest[i] >= k) {
				int rst = rest[i];
				rest[i] -= k;
				return new int[] { i, m - rst };
			}
		}
		return null;
	}

	public boolean scatter(int k, int maxRow) {
		long sum = 0;
		for (int i = 0; i <= maxRow; i++) {
			sum += this.rest[i];
		}
		if (sum >= k) {
			for (int i = 0; i <= maxRow && k > 0; i++) {
				int diff = Math.min(this.rest[i], k);
				this.rest[i] -= diff;
				k -= diff;
			}
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		BookMyShow bms = new BookMyShow(5, 9); // 总共有 2 排，每排 5 个座位。
		bms.gather(10, 1); // 返回 [0, 0]

		bms.scatter(3, 3); // 返回 True
		bms.gather(9, 1); // 返回 []
		bms.gather(10, 2); // 返回 []
		bms.gather(2, 0); // 返回 []

	}

//	["BookMyShow","gather","scatter","gather","gather","gather"]
//	[[5,9],[10,1],[3,3],[9,1],[10,2],[2,0]]
	// [null,[],true,[1,0],[],[]]
	// [null,[],true,[1,0],[],[0,3]]

}
